//目标和  力扣494
//01背包dp 求装满背包有几种情况
class Solution {
public:
	int findTargetSumWays(vector<int>& nums, int target) {
		int sum = 0;
		for(int i = 0; i < nums.size(); i++)
			sum += nums[i];
		
		if(abs(target) > sum) return 0;
		if((sum + target) % 2 != 0) return 0;
		int bagsize = (sum + target) / 2;
		
		vector<vector<int>> dp(nums.size(),vector<int>(bagsize+1,0));
		if(nums[0] <= bagsize) dp[0][nums[0]] = 1;
		
		//dp[0][0] = 1;
		int zerosum = 0;
		for(int i = 0; i <nums.size(); i++)
		{
			if(nums[i] == 0) zerosum++;
			dp[i][0] = (int)pow(2.0,zerosum);
		}
		
		for(int i = 1; i < nums.size(); i++)
		{
			for(int j = 1; j <=bagsize; j++)
			{
				if(nums[i] > j)dp[i][j] = dp[i-1][j];
				else dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
			}
		}
		return dp[nums.size()-1][bagsize];
	}
};
